package cn.cxq.learning.array;

import org.junit.jupiter.api.Test;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Scanner;

/**
 * 名企编程真题(小米)
 * 计算题（计算接水量）
 * 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 64M，其他语言128M 热度指数：2491
 * 本题知识点： 前端工程师 小米 模拟 栈 贪心 2019
 *  算法知识视频讲解
 * 校招时部分企业笔试将禁止编程题跳出页面，为提前适应，练习时请使用在线自测，而非本地IDE。
 * 题目描述
 *
 * 给定n个非负整数表示每个宽度为1的柱子的高度题，计算按此排列的柱子，下雨之后能接多少雨水。
 * 输入描述:
 * 逗号分隔的整数，表示每根柱子的高度。
 * 柱子数n<=1000000,每根柱子的高度不大于100000
 * 输出描述:
 * 雨水量（高度和）
 * 示例1
 * 输入
 * 复制
 * 0,1,0,2,1,0,1,3,2,1,2,1
 * 输出
 * 复制
 * 6
 */
public class ReceiveRainwater {

    @Test
    public void test() {

        Scanner scanner = new Scanner(System.in);

        String line = scanner.nextLine();

        String[] split = line.split(",");

        int[] arr = new int[split.length];

        for (int i = 0; i < split.length; i++) {
            arr[i] = Integer.parseInt(split[i]);
        }

        System.out.println(receiveRainwater(arr));
    }

    // 思路：先将字符串分割，从前往后，选择第一个板作为参照，直到找到第二块比它高或者和它一样高的板在计算盛水量，
    // 记得计算损失量，将第二块板作为下一次的起始板，继续遍历；然后从后往前进行相同的遍历。
    public static void main(String[] args) {

        BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));

        String line = null;
        try {
            line = bufferedReader.readLine();
        } catch (IOException e) {
            e.printStackTrace();
        }

        String[] split = line.split(",");

        int[] arr = new int[split.length];

        for (int i = 0; i < split.length; i++) {
            arr[i] = Integer.parseInt(split[i]);
        }

        System.out.println(receiveRainwater(arr));
    }

    public static long receiveRainwater(int[] arr) {

        if (arr.length == 0) {
            return 0;
        }

        long amount = 0;
        int start = 0;
        while (true) {
            int index = start + 1;
            if (index == arr.length) {
                break;
            }
            long deBuff = 0;
            while (index < arr.length) {
                if (arr[start] <= arr[index]) {
                    break;
                }
                deBuff += arr[index];
                index++;
            }
            if (index == arr.length) {
                break;
            }
            amount += (long) (index - start - 1) * (arr[start] > arr[index] ? arr[index] : arr[start]) - deBuff;
            start = index;
        }

        int end = start - 1;
        start = arr.length - 1;
        while (true) {
            int index = start - 1;
            if (index == end) {
                break;
            }
            long deBuff = 0;
            while (index > end) {
                if (arr[start] <= arr[index]) {
                    break;
                }
                deBuff += arr[index];
                index--;
            }
            if (index == end) {
                break;
            }
            amount += (long) (start - index - 1) * (arr[start] > arr[index] ? arr[index] : arr[start]) - deBuff;
            start = index;
        }

        return amount;
    }
}
